package com.antSort;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;
import java.util.logging.Level;
import java.util.logging.Logger;

public class data {
    private  int k;//总项目编号，用于遍历宽度与长度数据
    private  final ArrayList<Integer> l = new ArrayList<>();//final 修饰可以保证变量的引用不会被改变
    private  final ArrayList<Integer> w = new ArrayList<>();
    private  final ArrayList<Integer> v = new ArrayList<>();
    private  final ArrayList<Integer> r = new ArrayList<>();
    private  final ArrayList<int[]> setO=new ArrayList<>();
    private  final ArrayList<int[]> goalJ =new ArrayList<>();//目标矩形对应标号
    private  final ArrayList<int[]> allJ=new ArrayList<>();//所有可能矩形的编号及长宽

    public ArrayList<int[]> getSetO() {
        return setO;
    }

    public ArrayList<int[]> getGoalJ() {
        return goalJ;
    }

    public ArrayList<int[]> getAllJ() {
        return allJ;
    }

    public int getK() {
        return k;
    }

    public int[] getL() {
        int[] intArray = new int[l.size()];
        for (int i = 0; i < l.size(); i++) {
            intArray[i] = l.get(i);
        }
        return intArray;
    }

    public  int[] getW() {
        int[] intArray = new int[w.size()];
        for (int i = 0; i < w.size(); i++) {
            intArray[i] = w.get(i);
        }
        return intArray;
    }

    public  int[] getR() {
        int[] intArray = new int[v.size()];
        for (int i = 0; i < r.size(); i++) {
            intArray[i] = r.get(i);
        }
        return intArray;
    }

    public  int[] getV() {
        int[] intArray = new int[r.size()];
        for (int i = 0; i < v.size(); i++) {
            intArray[i] = v.get(i);
        }
        return intArray;
    }

    public  void readFile(String path,int reductionsMethod) throws Exception {
        try (BufferedReader br = new BufferedReader(new FileReader(path))) {
            String line;
            while ((line = br.readLine()) != null) {
                if (line.trim().isEmpty()) {
                    continue; // 跳过空行
                }
                // 使用空格分割每一列的内容
                String[] parts = line.split("\\s+");
                if (parts.length==1){
                    k = Integer.parseInt(parts[0].trim());   //获取项目数量
                }
                if (parts.length==2){
                    l.add(Integer.parseInt(parts[0].trim()));
                    w.add(Integer.parseInt(parts[1].trim()));
                    r.add(0);
                    v.add(0);
                }
                if (parts.length==4){
                    l.add(Integer.parseInt(parts[0].trim()));
                    w.add(Integer.parseInt(parts[1].trim()));
                    r.add(Integer.parseInt(parts[3].trim()));
                    v.add(Integer.parseInt(parts[2].trim()));
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }//获取

        ArrayList<Integer> setVQ=new ArrayList<>();
        ArrayList<Integer> setHQ=new ArrayList<>();
        if (reductionsMethod==1){
            setVQ=combination(l,l.get(0));;//竖向切割集合
            setHQ=combination(w,w.get(0));//横向切割集合
        }else {
             setVQ=combinationQR(l,l.get(0));;//竖向切割集合
             setHQ=combinationQR(w,w.get(0));//横向切割集合
        }

        allJ.add(new int[]{l.get(0),w.get(0)});
        HashSet<Integer> tmp=new HashSet<>();
        tmp.add(0);//存储索引值
        updateSetJ(tmp,setHQ,setVQ);

        for (int i=0;i<allJ.size();i++){
            for (int j=0;j<l.size();j++){
                if (allJ.get(i)[0]==l.get(j) && allJ.get(i)[1]==w.get(j)){
                    goalJ.add(new int[]{i,v.get(j), r.get(j)});//索引、价值、次数
                }
            }
        }
//        for (int[] list:goalJ){
//            System.out.println(list[0]+"对应长宽为"+allJ.get(list[0])[0]+"与"+allJ.get(list[0])[1]);
//        }
//        System.out.println("总项目数为"+k);//查询读取信息
//        System.out.println("大矩形长为"+l.get(0)+";"+"大矩形宽为"+w.get(0));
//        for (int i = 1; i <k+1; i++) {
//            System.out.println("第"+i+"个矩形的数据为"+l.get(i)+","+w.get(i)+","+r.get(i)+","+v.get(i));
//        }
//        for (int i=0;i<allJ.size();i++){
//            System.out.println("第"+i+"块矩形的长宽分别为"+allJ.get(i)[0]+"与"+allJ.get(i)[1]);
//        }
//        System.out.println("目标矩形块对应的索引值为："+goalJ);
//        for (int i:goalJ){
//                    System.out.println(i);
//                    System.out.println("第"+i+"块矩形的长宽分别为"+allJ.get(i)[0]+"与"+allJ.get(i)[1]);
//        }
    }

    private  void updateSetJ(HashSet<Integer> tmp,ArrayList<Integer> setHQ, ArrayList<Integer> setVQ){
        if(tmp.isEmpty()){
            return;
        }
        Iterator<Integer> iter= tmp.iterator();
        HashSet<Integer> newIndices = new HashSet<>();//用于存储新索引
        HashSet<Integer> oldIndices = new HashSet<>();//用于存储预去除的索引
        while (iter.hasNext()){
            int index = iter.next();
            int indexL=allJ.get(index)[0];
            int indexW=allJ.get(index)[1];
            oldIndices.add(index);
            //o=0,横切
            for (Integer newW1 :setHQ){
                if (newW1 <indexW){
                    int newW2=indexW- newW1;
                    int[] newRec1=new int[]{indexL,newW1};
                    int[] newRec2=new int[]{indexL,newW2};
                    if (Arrays.equals(newRec1,newRec2)){//若产生的两个矩形一样，则仅添加一个到allJ，否则，两个均做判断后添加
                        if (containJudge(newRec1)){
                            allJ.add(newRec1);
                            newIndices.add(allJ.size()-1);
                        }
                    }else {//对产生的上下两个矩形块分开进行比较，并将符合条件的添加到allJ中
                        if (containJudge(newRec1)){
                            allJ.add(newRec1);
                            newIndices.add(allJ.size()-1);
                        }
                        if (containJudge(newRec2)){
                            allJ.add(newRec2);
                            newIndices.add(allJ.size()-1);
                        }
                    }
                    setO.add(new int[]{0,newW1,index});//对切割方式进行保存
                }
            }
            //o=1,竖切
            for (Integer newL1 :setVQ){
                if (newL1 <indexL){
                    int newL2=indexL - newL1;
                    int[] newRec1=new int[]{newL1,indexW};
                    int[] newRec2=new int[]{newL2,indexW};
                    if (containJudge(newRec1)){
                        allJ.add(newRec1);
                        newIndices.add(allJ.size()-1);
                    }
                    if (containJudge(newRec2)){
                        allJ.add(newRec2);
                        newIndices.add(allJ.size()-1);
                    }
                    setO.add(new int[]{1,newL1,index});
                }
            }
        }
        tmp.addAll(newIndices);
        tmp.removeAll(oldIndices);
        newIndices.clear();
        oldIndices.clear();
        updateSetJ(tmp,setHQ, setVQ);
    }


    // 判断是否包含有效项目(fit some item):
    private  boolean containJudge(int[] list) {
        for (int i = 1; i < l.size(); i++) {
            if (list[0]>=l.get(i)&&list[1]>=w.get(i) && contain_array(allJ,list)){
                return true;
            }
        }
        return false;
    }

    // 判断矩形集合中是否包含指定的矩形：
    private  boolean contain_array(ArrayList<int[]> arrayList, int[] targetArray) {
        for (int[] array : arrayList) {
            if (Arrays.equals(array, targetArray)) {
                return false;//表示包含
            }
        }
        return true;
    }

    private  ArrayList<Integer> combination(ArrayList<Integer> L,int item){
        ArrayList<Integer> list=new ArrayList<>();
        int[] dp=new int[item+1];//dp[i]表示i能否组合获得
        Arrays.fill(dp, -1);//标记不能组合获取的数据，先假设全部不能组合获得
        for (int tmp:L){
            dp[tmp]=1;
        }
        for (int i = 1; i <=item; i++) {
            if (dp[i]!=-1){
                for (int j = 0; j < L.size(); j++) {//可能需要加limit
                    if (i+L.get(j)<=item && dp[i+L.get(j)]!=1){
                        dp[i+L.get(j)]=1;
                    }
                }
            }
        }
        for (int i = 1; i <=item; i++){
            if (dp[i]==1){
                list.add(i);
            }
        }
        if (list.get(list.size()-1)==item){
            list.remove(list.size()-1);
        }
        return list;
    }
    private  ArrayList<Integer> combinationQR(ArrayList<Integer> L,int item){
        ArrayList<Integer> list=new ArrayList<>();
        list.addAll(L);
        return list;
    }
}